/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

// 解法1： BFS
 function levelOrder(root: TreeNode | null): number[][] {
     if(!root){
         return [];
     }
    //  维护一个遍历调用栈
     let queue:TreeNode[] = [root];
    //  放所有的结果
     let results:number[][] = [];
     while(queue.length){
        //  用来临时存放 当前一层的结果
         let tempVals:number[] = [];
        //  用来临时存放下一层的所有节点
         let nextNodes:TreeNode [] =[];
        
        // queue中存储的是当前层的所有节点列表，一次遍历，处理掉当前队列中，当前层的所有节点
         while(queue.length){
            let currNode:TreeNode = queue.shift();
            tempVals.push(currNode.val);
            // 将该节点的子节点放到下一层的队列中
            currNode.left && nextNodes.push(currNode.left);
            currNode.right && nextNodes.push(currNode.right);
         }
        //  存入，当前层的所有val
         results.push(tempVals);

        //  将下一层的所有节点放入队列中，进入下一次循环
         queue.push(...nextNodes);
     }
     return results;
};

// 解法2：DFS
function levelOrder2(root: TreeNode | null): number[][] {
    if(!root){
        return [];
    }
    // 用于存放所有的val
    let results:number[][] = [];
    bfs(root,0,results);
    return results;
};
// node是当前遍历的节点
// deep 是当前层的深度
function bfs(node:TreeNode,deep:number,results:number[][]) {
    if(!node){
        return;
    }
    // 如果当前层还没有值，就给当前层创建也给空数组，然后当前节点放进入；
    // 如果当前层有值，直接把数据放进当前层的数组中。
    results[deep] ? results[deep].push(node.val): results[deep] = [node.val];
    // 进行遍历
    bfs(node.left,deep+1,results);
    bfs(node.right, deep+1,results);
}